package com.coder.algorithm.offer_2;

import java.util.Locale;

/**
 * 机器人的运动范围
 *
 * @author yuhushuan
 * @date 2020/6/9 21:52
 */
public class _13_1_RobotMove {
    public static void main(String[] args) {
        // 功能测试（方格为多行多列；k 为正数）

        print(4, 2, 2);
        print(4, 10, 10);
        print(8, 20, 20);
        print(9, 20, 20);

        // 边界值测试（方格只有一行或者只有一列；k 等于 0）
        print(4, 20, 1);
        print(0, 2, 2);
        print(-1, 2, 2);
    }

    private static void print(int threshold, int rows, int cols) {
        System.out.println(String.format(Locale.getDefault(),
                "\n在 %d 行 %d 列的格子中，机器人在位数和不大于 %d 的运动范围为",
                rows, cols, threshold));
        int sum = movingCount(threshold, rows, cols);
        System.out.println(String.format(Locale.getDefault(),
                "共 %d 个格子", sum));
    }

    private static void printVisited(boolean[] visited, int rows, int cols) {
        for (int row = 0; row < rows; ++row) {
            for (int col = 0; col < cols; ++col) {
                System.out.print(visited[row * cols + col] ? " 1 " : " 0 ");
            }
            System.out.println();
        }
    }

    private static int movingCount(int threshold, int rows, int cols) {
        if (threshold < 0 || rows <= 0 || cols <= 0) {
            return 0;
        }
        boolean[] visited = new boolean[rows * cols];
        int result = movingCountCore(threshold, rows, cols, 0, 0, visited);
        printVisited(visited, rows, cols);
        return result;
    }

    private static int movingCountCore(int threshold, int rows, int cols, int row, int col,
                                       boolean[] visited) {
        int count = 0;
        if (check(threshold, rows, cols, row, col, visited)) {
            visited[row * cols + col] = true;

            count = 1 + movingCountCore(threshold, rows, cols, row, col - 1, visited)
                    + movingCountCore(threshold, rows, cols, row, col + 1, visited)
                    + movingCountCore(threshold, rows, cols, row - 1, col, visited)
                    + movingCountCore(threshold, rows, cols, row + 1, col, visited);
        }
        return count;
    }

    private static boolean check(int threshold, int rows, int cols, int row, int col, boolean[] visited) {
        if (row >= 0 && row < rows && col >= 0 && col < cols
                && getDigitSum(row) + getDigitSum(col) <= threshold
                && !visited[row * cols + col]) {
            return true;
        }
        return false;
    }

    private static int getDigitSum(int number) {
        int sum = 0;
        while (number > 0) {
            sum += number % 10;
            number /= 10;
        }
        return sum;
    }
}
